package com.sheng.leetcode.year2022.month10.day20;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/10/20
 *<p>
 * 779. 第K个语法符号<p>
 *<p>
 * 我们构建了一个包含 n 行( 索引从 1  开始 )的表。首先在第一行我们写上一个 0。<p>
 * 接下来的每一行，将前一行中的0替换为01，1替换为10。<p>
 * 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。<p>
 * 给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）<p>
 *<p>
 * 示例 1:<p>
 * 输入: n = 1, k = 1<p>
 * 输出: 0<p>
 * 解释: 第一行：0<p>
 *<p>
 * 示例 2:<p>
 * 输入: n = 2, k = 1<p>
 * 输出: 0<p>
 * 解释:<p>
 * 第一行: 0<p>
 * 第二行: 01<p>
 *<p>
 * 示例 3:<p>
 * 输入: n = 2, k = 2<p>
 * 输出: 1<p>
 * 解释:<p>
 * 第一行: 0<p>
 * 第二行: 01<p>
 *<p>
 * 提示:<p>
 * 1 <= n <= 30<p>
 * 1 <= k <= 2^(n - 1)<p>
 */
public class LeetCode0779 {

    @Test
    public void test01() {
//        int n = 1, k = 1;
//        int n = 2, k = 1;
        int n = 2, k = 2;
        System.out.println(new Solution().kthGrammar(n, k));
    }
}
class Solution {
    // 判断是否需要反转
    boolean flag = false;
    public int kthGrammar(int n, int k) {
        /**
         * 0 -> 01       1 -> 10
         * 1(2^0): 0
         * 2(2^1): 0 1
         * 3(2^2): 01 10
         * 4(2^3): 0110 1001
         * 5(2^4): 01101001 10010110
         * 6(2^5): 0110100110010110 1001011001101001
         * 规矩：第 n 次转换和第 n - 1 次相比较，前半部分完全相同，后半部分相比第 n - 1 次完全相反
         * (索引从 1 开始)第 n 次时，总长度为 2^(n - 1)
         * 试试化简：比如 n = 6 时，我如果要找 16 位以前的，那么我可以直接找 n = 5 的同位置值，如果我要找的值大于 16 位，那么我就找 n = 5 时， k - 2^4 位置的元素的相反值
         */
        if (n > 1) {
            double pow = Math.pow(2, n - 2);
            if (k > pow) {
                // 如果 k 大于第 n 次时字符串总长度的一半，那么意味者迭代的时候要减去这一半，然后在 n - 1 的位置找到对应的值，并且要取反
                k -= pow;
                if (flag) {
                    flag = false;
                } else {
                    flag = true;
                }
            }
            // 迭代下去，一直到 n == 1 为止
            return kthGrammar(n - 1, k);
        } else {
            // 通过是否反转，判断返回元素的值
            if (flag) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}
